package Traverse.traverse;

import domain.TreeNode;

import java.util.Stack;

/**
 *
 * 先序遍历
 * Created by 雷文康 on 2018/1/14.
 */
public class PreOrder {
    /*
     1
   2    3
 4  5  6  7

 */
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node4.right = null;
        node5.left = node5.right = null;
        node6.left = node6.right = null;
        node7.left = node7.right = null;
        preOrder(node1);
        System.out.println();
        preOrder2(node1);
        System.out.println();
        preOrder3(node1);
    }

    public static void preOrder(TreeNode root) {
         if (root == null){
             return;
         }
        System.out.print(root.val);
        System.out.print(" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void preOrder2(TreeNode root) {
        if (root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val);
            System.out.print(" ");
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }
    }


    public static void preOrder3(TreeNode root) {
        if (root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                System.out.print(p.val);
                System.out.print(" ");
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                p = p.right;
            }
        }

    }

}
